Ja, willkommen zur vorletzten Vorlesung Kompalk dieses Jahr.

Wir machen weiterhin Freestyle, nicht?

Wir haben nichts mehr zu tun mit den Aufgaben und selbstverständlich stelle ich auch zu

Dingen, die nicht in den Aufgaben rankommen, keine Klausuraufgaben.

Also machen wir weiterhin Dinge, die Spaß machen.

Beziehungsweise mache ich auch so ein bisschen Werbung für Dinge, die näher an der Thematik

von Lehrstuhl 8 liegen.

Ich habe schon mal erzählt, nicht wahr, die theoretische Informatik ist unterteilt in

A und B klassischerweise.

A ist Algorithmen und Komplexität, also das, was wir hier tun.

B ist Logik und Semantik.

Nur ist es nicht so, als hätte Logik mit Komplexität nichts zu tun.

Nur, dass sich Logiker typischerweise für Komplexitätsklassen interessieren, die etwas

oberhalb dessen liegen, was den üblichen Komplexitätstheoretiker interessiert.

Also nach Ansicht der Komplexitätstheoretiker fängt dabei in NP an, das an, was man Intractability

nennt.

Das ist nicht wirklich die Sichtweise, die der Logiker einnehmen kann, denn schon die

dusseligste aller rumliegenden Logiken, schlichter Aussagen, Logik ist ja NP-hart.

Und viele Dinge, für die sich der Logiker interessiert, sind also in der Komplexität

weit oberhalb von NP bis eben hin zur Unentscheidbarkeit, im Falle von zum Beispiel bereits Logik 1.

Stufe.

Aber es gibt auch viele entscheidbare Logiken, die durchaus auch von praktischem Interesse

sind, die Komplexitäten haben deutlich oberhalb von NP, zum Beispiel eben P-Space.

Das sind insbesondere Logiken, die im Semantik Web eine Rolle spielen, nochmal in Bezug auf

nächstes Semester angebotene Veranstaltungen, einerseits Ontologien im Semantik Web, andererseits

Praktikum Wissensrepräsentation.

Die Sprachen, die da verwendet werden, haben verschiedene Komplexitäten, je nachdem wie

viel von ihrer Ausdrucksmächtigkeit man verwendet.

Selbst wenn man von OWL praktisch gar keine Features verwendet, ist es zum Beispiel P-Space

vollständig, daher also das Interesse in dieser Klasse, das wir jetzt hier in der letzten

Woche verfolgen wollen.

Zum Beispiel die aktuelle Version OWL 2, ich glaube das einzige was man komplexitätstheoretisch

über sie weiß, ist, dass sie doppelt nx time hard ist oder irgend so was in der Richtung.

Obere Schranke kennt man glaube ich keine.

Also es sind komplexe Logiken, trotzdem sollte man sich davon nicht abschrecken lassen, es

gibt eben Reasoner, die auch mit expressiven Fragmenten von OWL effizient umgehen können

in den Fällen, die man praktisch so findet.

Gut, ja, also P-Space Vollständigkeit.

Wir kennen ja schon verschiedene vollständige Probleme für kleinere oder niedrigere Komplexitätsklassen,

die im Wesentlichen Logiken sind.

Ja, ganz bekannt eben hier nicht NP-vollständig, das überhaupt ursprüngliche NP-vollständige

Problem ist das Sattproblem, also im Wesentlichen Schlussfolger in Aussagenlogik.

Zwingensweise das Gegenteil von Schlussfolgern, also Erfüllbarkeitschecken heißt ja im Wesentlichen

prüfen, dass bestimmte Schlussfolgerungen nicht gelten, entsprechend Schlussfolgern

in Aussagenlogik, also QNP-vollständig.

Was wir hier nicht gemacht haben, ist das, wenn man das Sattproblem einschränkt auf

sogenannte Hornklauseln, in denen also pro Klausel höchstens ein oder nicht Hornklauseln,

sondern Hornformeln, das heißt also solche CNFs, in denen pro Klausel höchstens ein positives

Literal vorkommt, dann bekommt man ein P-vollständiges Problem, Hornsatt, also Erfüllbarkeit von

Hornformeln.